{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize Hamming Distance After Swap Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #union-find #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #并查集 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumHammingDistance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #执行交换操作后的最小汉明距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数数组 <code>source</code> 和 <code>target</code> ，长度都是 <code>n</code> 。还有一个数组 <code>allowedSwaps</code> ，其中每个 <code>allowedSwaps[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示你可以交换数组 <code>source</code> 中下标为 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code>（<strong>下标从 0 开始</strong>）的两个元素。注意，你可以按 <strong>任意</strong> 顺序 <strong>多次</strong> 交换一对特定下标指向的元素。</p>\n",
    "\n",
    "<p>相同长度的两个数组 <code>source</code> 和 <code>target</code> 间的 <strong>汉明距离</strong> 是元素不同的下标数量。形式上，其值等于满足 <code>source[i] != target[i]</code> （<strong>下标从 0 开始</strong>）的下标 <code>i</code>（<code>0 &lt;= i &lt;= n-1</code>）的数量。</p>\n",
    "\n",
    "<p>在对数组 <code>source</code> 执行 <strong>任意</strong> 数量的交换操作后，返回 <code>source</code> 和 <code>target</code> 间的 <strong>最小汉明距离</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>source 可以按下述方式转换：\n",
    "- 交换下标 0 和 1 指向的元素：source = [<strong>2</strong>,<strong>1</strong>,3,4]\n",
    "- 交换下标 2 和 3 指向的元素：source = [2,1,<strong>4</strong>,<strong>3</strong>]\n",
    "source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>不能对 source 执行交换操作。\n",
    "source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == source.length == target.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= source[i], target[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= allowedSwaps.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>allowedSwaps[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n - 1</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-hamming-distance-after-swap-operations](https://leetcode.cn/problems/minimize-hamming-distance-after-swap-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-hamming-distance-after-swap-operations](https://leetcode.cn/problems/minimize-hamming-distance-after-swap-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n[2,1,4,5]\\n[[0,1],[2,3]]', '[1,2,3,4]\\n[1,3,2,4]\\n[]', '[5,1,2,4,3]\\n[1,5,4,2,3]\\n[[0,4],[4,2],[1,3],[1,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    class UF:\n",
    "        def __init__(self, sz):\n",
    "            self.parent = list(range(sz))\n",
    "\n",
    "        def find(self, x):\n",
    "            if x == self.parent[x]:\n",
    "                return x\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "            return self.parent[x]\n",
    "\n",
    "        def union(self, x, y):\n",
    "            xRoot, yRoot = self.find(x), self.find(y)\n",
    "            if xRoot == yRoot: return\n",
    "            self.parent[xRoot] = yRoot\n",
    "        \n",
    "        def isConnected(self, x, y):\n",
    "            return self.find(x) == self.find(y)\n",
    "\n",
    "    def minimumHammingDistance(self, src: List[int], tar: List[int], swaps: List[List[int]]) -> int:\n",
    "        n, same = len(src), 0\n",
    "        uf = Solution.UF(n)\n",
    "        for p in swaps:\n",
    "            uf.union(p[0], p[1])\n",
    "\n",
    "        split = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            # 找到当前下标的root，并记录当前下标\n",
    "            p = uf.find(i)\n",
    "            split[p].append(i)\n",
    "            \n",
    "        for p in split:\n",
    "            # 统计当前集合里，每个数字出现的次数\n",
    "            record = defaultdict(int)\n",
    "            for idx in split[p]:\n",
    "                record[src[idx]] += 1\n",
    "            # 统计完后才能遍历tar\n",
    "            for idx in split[p]:\n",
    "                cur = tar[idx]\n",
    "                if record[cur] > 0:\n",
    "                    same += 1\n",
    "                    record[cur] -= 1\n",
    "        return n - same"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        s = list(range(n))\n",
    "\n",
    "        def find(x):\n",
    "            if x != s[x]:\n",
    "                s[x] = find(s[x])\n",
    "            return s[x]\n",
    "        def union(x, y):\n",
    "            sx, sy = find(x), find(y)\n",
    "            if sx != sy:\n",
    "                s[sx] = sy \n",
    "        \n",
    "\n",
    "        for x, y in allowedSwaps:\n",
    "            union(x, y)\n",
    "        mp = defaultdict(Counter)\n",
    "        for i, x in enumerate(source):\n",
    "            si = find(i)\n",
    "            mp[si][x] += 1\n",
    "        res = len(target)\n",
    "        for i, x in enumerate(target):\n",
    "            si = find(i)\n",
    "            if mp[si][x] > 0:\n",
    "                res -= 1\n",
    "                mp[si][x] -= 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        u = self.Union()\n",
    "        for item in allowedSwaps:\n",
    "            u.merge(item[0], item[1])\n",
    "\n",
    "        m = {}\n",
    "        for i in range(0, len(source)):\n",
    "            idx = u.search(i)\n",
    "            if m.get(idx) is None:\n",
    "                m[idx] = {}\n",
    "            if m[idx].get(source[i]) is None:\n",
    "                m[idx][source[i]] = 1\n",
    "            else:\n",
    "                m[idx][source[i]] += 1\n",
    "        for i in range(0, len(target)):\n",
    "            idx = u.search(i)\n",
    "            if m[idx].get(target[i]) is not None:\n",
    "                m[idx][target[i]] -= 1\n",
    "                if m[idx][target[i]] == 0:\n",
    "                    del m[idx][target[i]]\n",
    "        sum = 0\n",
    "        for k in m:\n",
    "            for v in m[k]:\n",
    "                sum += m[k][v]\n",
    "        return sum\n",
    "\n",
    "\n",
    "    class Union:\n",
    "        def __init__(self):\n",
    "            self.map = {}\n",
    "\n",
    "        def merge(self, i, j: int):\n",
    "            pi, pj = self.search(i), self.search(j)\n",
    "            if pi != pj:\n",
    "                self.map[pj] = pi\n",
    "\n",
    "        def search(self, i: int) -> int:\n",
    "            pi = self.map.get(i)\n",
    "            if pi is None:\n",
    "                return i\n",
    "            ppi = self.map.get(pi)\n",
    "            if ppi != pi:\n",
    "                self.map[i] = self.search(pi)\n",
    "            return self.map[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        s = defaultdict(list)\n",
    "        t = defaultdict(list)\n",
    "\n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            for idx in root2idx[k]:\n",
    "                s = source[idx]\n",
    "                cnt[s] += 1\n",
    "            for idx in root2idx[k]:\n",
    "                t = target[idx]\n",
    "                if cnt[t] > 0:\n",
    "                    cnt[target[idx]] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            ans += sum(cnt.values())\n",
    "        \n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            for idx in root2idx[k]:\n",
    "                s = source[idx]\n",
    "                cnt[s] += 1\n",
    "            for idx in root2idx[k]:\n",
    "                t = target[idx]\n",
    "                if cnt[t] > 0:\n",
    "                    cnt[target[idx]] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            ans += sum(cnt.values())\n",
    "        \n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            for idx in root2idx[k]:\n",
    "                s = source[idx]\n",
    "                cnt[s] += 1\n",
    "            for idx in root2idx[k]:\n",
    "                t = target[idx]\n",
    "                if cnt[t] > 0:\n",
    "                    cnt[target[idx]] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            ans += sum(cnt.values())\n",
    "        \n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            for idx in root2idx[k]:\n",
    "                s = source[idx]\n",
    "                cnt[s] += 1\n",
    "            for idx in root2idx[k]:\n",
    "                t = target[idx]\n",
    "                if cnt[t] > 0:\n",
    "                    cnt[target[idx]] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            ans += sum(cnt.values())\n",
    "        \n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [0] * n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.r[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        \n",
    "        n = len(source)\n",
    "\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            tmp = 0\n",
    "            for idx in root2idx[k]:\n",
    "                x = source[idx]\n",
    "                cnt[x] += 1\n",
    "            \n",
    "            for idx in root2idx[k]:\n",
    "                y = target[idx]\n",
    "                if cnt[y] > 0:\n",
    "                    cnt[y] -= 1\n",
    "                else:\n",
    "                    tmp += 1\n",
    "            ans += (tmp + sum(cnt.values()))\n",
    "        \n",
    "        return ans // 2\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]):\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        root2idx = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            root2idx[root].append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for k in root2idx:\n",
    "            cnt = Counter()\n",
    "            for idx in root2idx[k]:\n",
    "                s = source[idx]\n",
    "                cnt[s] += 1\n",
    "            for idx in root2idx[k]:\n",
    "                t = target[idx]\n",
    "                if cnt[t] > 0:\n",
    "                    cnt[target[idx]] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            ans += sum(cnt.values())\n",
    "        \n",
    "        return ans // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        # 并查集\n",
    "        n = len(source)\n",
    "        fa = list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        for x,y in allowedSwaps:\n",
    "            a = find(x)\n",
    "            b = find(y)\n",
    "            if a != b:\n",
    "                fa[a] = b\n",
    "        # 同一父节点的放在一起\n",
    "        g = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a = find(i)\n",
    "            g[a].append(i)\n",
    "        # 枚举连通的\n",
    "        res = 0\n",
    "        for _,k in g.items():\n",
    "            a = [source[i] for i in k]\n",
    "            b = Counter(target[i] for i in k)\n",
    "            for c in a:\n",
    "                if b[c] > 0:\n",
    "                    b[c] -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        # 并查集\n",
    "        parent = list(range(n))\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "        # 连接\n",
    "        for x,y in allowedSwaps:\n",
    "            a,b = find(x),find(y)\n",
    "            if a != b:\n",
    "                parent[b] = a\n",
    "        # 遍历每个节点,然后储存到父节点中\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a = find(i)\n",
    "            dic[a].append(i)\n",
    "        # 统计结果\n",
    "        res = 0\n",
    "        for k,v in dic.items():\n",
    "            # 每个儿子的值\n",
    "            a = [source[i] for i in v]\n",
    "            b = Counter(target[i] for i in v)\n",
    "            for c in a:\n",
    "                if b[c] > 0:\n",
    "                    b[c] -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def find(self, parent:list[int], x:int):\n",
    "        if x==parent[x]:\n",
    "            return parent[x]\n",
    "        parent[x]=self.find(parent, parent[x])\n",
    "        return parent[x]\n",
    "    \n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent=[i for i in range(n)]\n",
    "        for l, r in allowedSwaps:\n",
    "            pl=self.find(parent, l)\n",
    "            pr=self.find(parent, r)\n",
    "            if pl!=pr:\n",
    "                parent[pr]=pl\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=self.find(parent, i)\n",
    "            dic[a].append(i)\n",
    "        \n",
    "        res=0\n",
    "        for k, v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=collections.Counter([target[i] for i in v])\n",
    "            for c in a:\n",
    "                if b[c] >0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        kkk=setUnion(n)\n",
    "        for i,j in allowedSwaps:\n",
    "            kkk.union(i,j)\n",
    "        part=kkk.get_partset()\n",
    "        ans=0\n",
    "        for p in part:\n",
    "            part[p]=Counter([source[i] for i in part[p]])\n",
    "        for i in range(n):\n",
    "            cur=kkk.find(i)\n",
    "            if cur in part:\n",
    "                cnt=part[cur][target[i]]\n",
    "                if cnt>0:\n",
    "                    part[cur][target[i]]-=1\n",
    "                else:\n",
    "                    ans+=1\n",
    "            else: ans+=source[i]!=target[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = p[p[x]]\n",
    "                x = p[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            p[find(y)] = find(x)\n",
    "        \n",
    "        for a, b in allowedSwaps:\n",
    "            union(a, b)\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            x = find(i)\n",
    "            d[x].append(i)\n",
    "        # print(d)\n",
    "        ans = 0\n",
    "        for k, v in d.items():\n",
    "            x = [source[i] for i in v]\n",
    "            y = Counter([target[i] for i in v])\n",
    "            for c in x:\n",
    "                if y[c]:\n",
    "                    y[c] -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class setUnion(object):\n",
    "    def __init__(self,size):\n",
    "        self.parent=list(range(size))\n",
    "        self.rank=[1]*size\n",
    "        self.setCount=size\n",
    "    def find(self,i):\n",
    "        if self.parent[i]==i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parent[i]=self.find(self.parent[i])\n",
    "            return self.parent[i]\n",
    "    def union(self,i,j):\n",
    "        x,y=self.find(i),self.find(j)\n",
    "        if x==y:\n",
    "            return\n",
    "        if self.rank[x]<self.rank[y]:\n",
    "            x,y=y,x\n",
    "        self.rank[x]+=self.rank[y]\n",
    "        self.parent[y]=x\n",
    "        self.setCount-=1\n",
    "    def is_connected(self,i,j):\n",
    "        return self.find(i)==self.find(j)\n",
    "    def get_partset(self):\n",
    "        part=defaultdict(list)\n",
    "        for i in range(len(self.parent)):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        kkk=setUnion(n)\n",
    "        for i,j in allowedSwaps:\n",
    "            kkk.union(i,j)\n",
    "        part=kkk.get_partset()\n",
    "        ans=0\n",
    "        for p in part:\n",
    "            part[p]=Counter([source[i] for i in part[p]])\n",
    "        for i in range(n):\n",
    "            cur=kkk.find(i)\n",
    "            if cur in part:\n",
    "                cnt=part[cur][target[i]]\n",
    "                if cnt>0:\n",
    "                    part[cur][target[i]]-=1\n",
    "                else:\n",
    "                    ans+=1\n",
    "            else: ans+=source[i]!=target[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if f[x]!=x:\n",
    "                f[x]=find(f[x])\n",
    "            return f[x]\n",
    "        def union(x,y):\n",
    "            f[find(x)]=find(y)\n",
    "        n=len(source)\n",
    "        f=list(range(n))\n",
    "        for a,b in allowedSwaps:\n",
    "            union(a,b)\n",
    "        d=defaultdict(list)\n",
    "        for i in range(n):\n",
    "            d[find(i)].append(i)\n",
    "        res=0\n",
    "        for A in d.values():\n",
    "            ct1=Counter(source[i] for i in A)\n",
    "            ct2=Counter(target[i] for i in A)\n",
    "            res+=len(A)-sum((ct1&ct2).values())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.f = list(range(n))\n",
    "        self.r = [1] * n\n",
    "    \n",
    "\n",
    "    def find(self, x):\n",
    "        if self.f[x] != x:\n",
    "            self.f[x] = self.find(self.f[x])\n",
    "        return self.f[x]\n",
    "    \n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if self.r[x] < self.r[y]:\n",
    "            self.f[x] = y\n",
    "        elif self.f[x] > self.r[y]:\n",
    "            self.f[y] = x\n",
    "        else:\n",
    "            self.f[y] = x\n",
    "            self.r[x] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "\n",
    "        n = len(source)\n",
    "        uf = UF(n)\n",
    "        for x, y in allowedSwaps:\n",
    "            if uf.find(x) != uf.find(y):\n",
    "                uf.union(x, y)\n",
    "        \n",
    "        s = defaultdict(list)\n",
    "        t = defaultdict(list)\n",
    "\n",
    "        for i in range(n):\n",
    "            root = uf.find(i)\n",
    "            s[root].append(source[i])\n",
    "            t[root].append(target[i])\n",
    "\n",
    "        ans = 0\n",
    "        for k in s.keys():\n",
    "            cnts = Counter(s[k])\n",
    "            cntt = Counter(t[k])\n",
    "            ans += sum((cnts - cntt).values())\n",
    "            ans += sum((cntt - cnts).values())\n",
    "\n",
    "        \n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        p = [i for i in range(n)]\n",
    "        \n",
    "        def find(x):\n",
    "            while x != p[x]:\n",
    "                p[x] = p[p[x]]\n",
    "                x = p[x]\n",
    "            return x\n",
    "        \n",
    "        def union(x, y):\n",
    "            p[find(y)] = find(x)\n",
    "        \n",
    "        for a, b in allowedSwaps:\n",
    "            union(a, b)\n",
    "        \n",
    "        d = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            x = find(i)\n",
    "            d[x].append(i)\n",
    "        # print(d)\n",
    "        cnt = 0\n",
    "        for v in d.values():\n",
    "            a = Counter(source[i] for i in v)\n",
    "            b = Counter(target[i] for i in v)\n",
    "            cnt += len(list((a&b).elements()))\n",
    "            \n",
    "        return n - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, Counter\n",
    "\n",
    "class Solution:\n",
    "    def find(self, x, parent):\n",
    "        if x != parent[x]:\n",
    "            parent[x] = self.find(parent[x], parent)\n",
    "        return parent[x]\n",
    "    \n",
    "    def union(self, x, y, parent, rank):\n",
    "        rootX = self.find(x, parent)\n",
    "        rootY = self.find(y, parent)\n",
    "        \n",
    "        if rootX != rootY:\n",
    "            if rank[rootX] > rank[rootY]:\n",
    "                parent[rootY] = rootX\n",
    "            elif rank[rootX] < rank[rootY]:\n",
    "                parent[rootX] = rootY\n",
    "            else:\n",
    "                parent[rootY] = rootX\n",
    "                rank[rootX] += 1\n",
    "\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        parent = [i for i in range(n)]\n",
    "        rank = [0] * n\n",
    "        \n",
    "        # Step 1: Build the union-find set using allowedSwaps\n",
    "        for x, y in allowedSwaps:\n",
    "            self.union(x, y, parent, rank)\n",
    "        \n",
    "        # Step 2: Group elements of source and target by their root in union-find set\n",
    "        group_source = defaultdict(list)\n",
    "        group_target = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            root = self.find(i, parent)\n",
    "            group_source[root].append(source[i])\n",
    "            group_target[root].append(target[i])\n",
    "            \n",
    "        # Step 3: Calculate the mismatches for each group\n",
    "        res = 0\n",
    "        for root in group_source:\n",
    "            count_source = Counter(group_source[root])\n",
    "            count_target = Counter(group_target[root])\n",
    "            for key, value in count_source.items():\n",
    "                res += max(0, value - count_target[key])\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        # 简单并查集\n",
    "        n = len(source)\n",
    "        p = [i for i in range(n)]\n",
    "\n",
    "        def find(node):\n",
    "            while p[node] != node:\n",
    "                p[node] = p[p[node]]\n",
    "                node = p[node]\n",
    "            return node\n",
    "\n",
    "        def union(a, b):\n",
    "            root_a, root_b = find(a), find(b)\n",
    "            if root_a != root_b:\n",
    "                p[root_a] = root_b\n",
    "        \n",
    "        for u, v in allowedSwaps:\n",
    "            union(u, v)\n",
    "        \n",
    "        m = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            m[find(i)].append(i)\n",
    "\n",
    "        ans = n\n",
    "        for k in m:\n",
    "            s = Counter([source[i] for i in m[k]])\n",
    "            t = Counter([target[i] for i in m[k]])\n",
    "            for k1 in s:\n",
    "                ans -= min(s[k1], t[k1])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        # 联通块 把在某个联通块的数值排序 比较 不在块里的 单独比较\n",
    "        ans = 0\n",
    "        n = len(source)\n",
    "        p = list(range(n))\n",
    "        single = [1]*n\n",
    "        def getP(x):\n",
    "            while x!= p[x]:\n",
    "                x = p[x]\n",
    "            return x\n",
    "        for x, y in allowedSwaps:\n",
    "            single[x]=single[y]=0\n",
    "            px = getP(x)\n",
    "            py = getP(y)\n",
    "            if px > py:\n",
    "                p[px] = py\n",
    "            elif px < py:\n",
    "                p[py] = px\n",
    "        d= defaultdict(list)\n",
    "        for i in range(n):\n",
    "            if single[i]:\n",
    "               ans += source[i]!=target[i]\n",
    "            else:\n",
    "                d[getP(i)].append(i)\n",
    "        for k, li in d.items():\n",
    "            a = Counter(source[i] for i in li)\n",
    "            b = Counter(target[i] for i in li) \n",
    "            t= 0\n",
    "            for k, v in a.items():\n",
    "                if k in b:\n",
    "                    t += min(v , b[k])\n",
    "            ans += len(li)-t \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        dc, c, n, res = {}, defaultdict(list), len(source), 0\n",
    "        def find(x):\n",
    "            if x not in dc: dc[x] = x\n",
    "            elif x != dc[x]: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        for i,j in allowedSwaps: dc[find(i)] = find(j)\n",
    "        for i in range(n):\n",
    "            if i in dc: c[find(i)].append(i)\n",
    "            elif source[i]!=target[i]: res += 1\n",
    "        for i in c:\n",
    "            lis, nc = c[i], defaultdict(int)\n",
    "            for j in lis:\n",
    "                nc[source[j]] += 1\n",
    "                nc[target[j]] -= 1\n",
    "            res += sum(i for i in nc.values() if i > 0)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n: int):\n",
    "        self.array = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, i: int):\n",
    "        \"\"\"查询i所属的连通分支\"\"\"\n",
    "        if self.array[i] != i:\n",
    "            self.array[i] = self.find(self.array[i])\n",
    "        return self.array[i]\n",
    "\n",
    "    def union(self, i: int, j: int):\n",
    "        \"\"\"合并i和j的连通分支\"\"\"\n",
    "        i = self.find(i)\n",
    "        j = self.find(j)\n",
    "        if self.size[i] >= self.size[j]:\n",
    "            self.array[j] = i\n",
    "            self.size[i] += self.size[j]\n",
    "        else:\n",
    "            self.array[i] = j\n",
    "            self.size[j] += self.size[i]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        size = len(source)\n",
    "\n",
    "        # 统计各个位置之间的连通性\n",
    "        dsu = DSU(size)\n",
    "        for n1, n2 in allowedSwaps:\n",
    "            dsu.union(n1, n2)\n",
    "\n",
    "        # 统计各个连通分支中的数量\n",
    "        count1 = collections.defaultdict(collections.Counter)\n",
    "        count2 = collections.defaultdict(collections.Counter)\n",
    "        for i in range(size):\n",
    "            idx = dsu.find(i)\n",
    "            count1[idx][source[i]] += 1\n",
    "            count2[idx][target[i]] += 1\n",
    "\n",
    "        # 计算每个连通分支中的差异数量\n",
    "        ans = 0\n",
    "        for idx in count1.keys():\n",
    "            c1 = count1[idx]\n",
    "            c2 = count2[idx]\n",
    "            total = 0  # 连通分支中元素数量总计\n",
    "            num = 0  # 连通分支中相同元素数量总计\n",
    "            for k in c1.keys():\n",
    "                total += c1[k]\n",
    "                num += min(c1[k], c2[k])\n",
    "            ans += total - num\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        parents = [i for i in range(n)]\n",
    "\n",
    "        def find(x):\n",
    "            parent = parents[x]\n",
    "            while parent != x:\n",
    "                return find(parent)\n",
    "            return parent\n",
    "\n",
    "        def union(x,y):\n",
    "            parent_x = find(x)\n",
    "            parent_y = find(y)\n",
    "            if parent_x != parent_y:\n",
    "                parents[parent_x] = parent_y\n",
    "        \n",
    "        for a in allowedSwaps:\n",
    "            x,y = a[0],a[1]\n",
    "            union(x,y)\n",
    "        \n",
    "        lookup = defaultdict(list)\n",
    "        for i,val in enumerate(parents):\n",
    "            lookup[find(i)].append(i)\n",
    "        \n",
    "\n",
    "        ans = 0\n",
    "        for k in lookup.keys():\n",
    "            c1 = Counter([source[i] for i in lookup[k]])\n",
    "            c2 = Counter([target[i] for i in lookup[k]])\n",
    "            ans += len(lookup[k]) - sum((c1&c2).values())\n",
    "        \n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in allowedSwaps:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "            \n",
    "        def dfs(node, fa):\n",
    "            vst[node] = 1\n",
    "            nodes.append(node)\n",
    "            for son in g[node]:\n",
    "                if son == fa:\n",
    "                    continue\n",
    "                dfs(son, node)\n",
    "        \n",
    "        vst = [0] * n\n",
    "        ret = 0\n",
    "        q = [0] * n\n",
    "        for i in range(n):\n",
    "            if vst[i]:\n",
    "                continue\n",
    "            \n",
    "            q[0] = i\n",
    "            vst[i] = 1\n",
    "            qh, qe = 0, 1\n",
    "            while qh < qe:\n",
    "                node = q[qh]\n",
    "                qh += 1\n",
    "                for son in g[node]:\n",
    "                    if vst[son]:\n",
    "                        continue\n",
    "                    q[qe] = son\n",
    "                    vst[son] = 1\n",
    "                    qe += 1\n",
    "            \n",
    "            cnt = Counter()\n",
    "            for node in q[:qe]:\n",
    "                cnt[source[node]] += 1\n",
    "                cnt[target[node]] -= 1\n",
    "            for k, v in cnt.items():\n",
    "                if v > 0:\n",
    "                    ret += v\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        # 并查集\n",
    "        n = len(source)\n",
    "        fa = list(range(n))\n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        for x,y in allowedSwaps:\n",
    "            a = find(x)\n",
    "            b = find(y)\n",
    "            if a != b:\n",
    "                fa[a] = b\n",
    "        # 同一父节点的放在一起\n",
    "        # g = defaultdict(list)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            a = find(i)\n",
    "            g[a].append(i)\n",
    "        # 枚举连通的\n",
    "        res = 0\n",
    "        for _,k in enumerate(g):\n",
    "            a = [source[i] for i in k]\n",
    "            b = Counter(target[i] for i in k)\n",
    "            for c in a:\n",
    "                if b[c] > 0:\n",
    "                    b[c] -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.part = n\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if self.size[root_x] >= self.size[root_y]:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        self.size[root_y] += self.size[root_x]\n",
    "        # 将非根节点的秩赋0\n",
    "        self.size[root_x] = 0\n",
    "        self.part -= 1\n",
    "        return True\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def get_root_part(self):\n",
    "        # 获取每个根节点对应的组\n",
    "        part = defaultdict(list)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            part[self.find(i)].append(i)\n",
    "        return part\n",
    "\n",
    "    def get_root_size(self):\n",
    "        # 获取每个根节点对应的组大小\n",
    "        size = defaultdict(int)\n",
    "        n = len(self.root)\n",
    "        for i in range(n):\n",
    "            size[self.find(i)] = self.size[self.find(i)]\n",
    "        return size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        uf = UnionFind(n)\n",
    "        for i, j in allowedSwaps:\n",
    "            uf.union(i, j)\n",
    "        ans = 0\n",
    "        group = uf.get_root_part()\n",
    "        for r in group:\n",
    "            cnt = Counter(source[i] for i in group[r])\n",
    "            dct = Counter(target[i] for i in group[r])\n",
    "            m = len(group[r])\n",
    "            res = 0\n",
    "            for num in set(list(cnt.keys())+list(dct.keys())):\n",
    "                res += min(cnt[num], dct[num])\n",
    "            ans += m-res\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent={i:i for i in range(n)}\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 搜索根节点\n",
    "        for l,r in allowedSwaps:\n",
    "            a,b=find(l),find(r)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "        # 获取根节点对应的连通块\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=find(i)\n",
    "            dic[a].append(i)\n",
    "        res=0\n",
    "        # 计算每个连通块对应的source元素与target的差集\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter([target[i] for i in v])\n",
    "            for c in a:\n",
    "                if b[c]>0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        f={i:i for i in range(n)}\n",
    "        def find(x):\n",
    "            if f[x]!=x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "\n",
    "        def union(i,j):\n",
    "            fi = find(i)\n",
    "            fj = find(j)\n",
    "            if fi!=fj:\n",
    "                f[fj] = fi\n",
    "\n",
    "        for l,r in allowedSwaps:\n",
    "            union(l,r)\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a = find(i)\n",
    "            dic[a].append(i)\n",
    "        ans = 0\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter(target[i] for i in v)\n",
    "            for c in a:\n",
    "                if b[c] >0:\n",
    "                    b[c]-=1\n",
    "\n",
    "                else:\n",
    "                    ans +=1\n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent={i:i for i in range(n)}\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 搜索根节点\n",
    "        for l,r in allowedSwaps:\n",
    "            a,b=find(l),find(r)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "        # 获取根节点对应的连通块\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=find(i)\n",
    "            dic[a].append(i)\n",
    "        res=0\n",
    "        # 计算每个连通块对应的source元素与target的差集\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter([target[i] for i in v])\n",
    "            for c in a:\n",
    "                if b[c]>0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent={i:i for i in range(n)}\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 搜索根节点\n",
    "        for l,r in allowedSwaps:\n",
    "            a,b=find(l),find(r)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "        # 获取根节点对应的连通块\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=find(i)\n",
    "            dic[a].append(i)\n",
    "        res=0\n",
    "        # 计算每个连通块对应的source元素与target的差集\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter([target[i] for i in v])\n",
    "            for c in a:\n",
    "                if b[c]>0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent={i:i for i in range(n)}\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 搜索根节点\n",
    "        for l,r in allowedSwaps:\n",
    "            a,b=find(l),find(r)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "        # 获取根节点对应的连通块\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=find(i)\n",
    "            dic[a].append(i)\n",
    "        res=0\n",
    "        # 计算每个连通块对应的source元素与target的差集\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter([target[i] for i in v])\n",
    "            for c in a:\n",
    "                if b[c]>0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        fa = [i for i in range(n)]\n",
    "        sz = [1] * n \n",
    "        \n",
    "        def find(x):\n",
    "            if fa[x] != x:\n",
    "                fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        \n",
    "        def merge(x, y):\n",
    "            fx, fy = find(x), find(y)\n",
    "            if fx != fy:\n",
    "                fa[fx] = fy\n",
    "                sz[fy] += sz[fx]\n",
    "            \n",
    "        for x, y in allowedSwaps:\n",
    "            merge(x, y)\n",
    "        ans = 0\n",
    "        g1, g2 = defaultdict(Counter), defaultdict(Counter)\n",
    "        for i, x, y in zip(range(n), source, target):\n",
    "            if i == find(i) and sz[i] == 1:\n",
    "                ans += x != y\n",
    "            else:\n",
    "                g1[find(i)][x] += 1\n",
    "                g2[find(i)][y] += 1\n",
    "        cnt = 0\n",
    "        for k in g1.keys():\n",
    "            for kk in (set(g1[k].keys()) | set(g2[k].keys())):\n",
    "                cnt += abs(g1[k][kk]-g2[k][kk])\n",
    "        ans += cnt // 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "'''\n",
    "--- 从此处复制 ---\n",
    "'''\n",
    "class IdentityDefaultDict(defaultdict):\n",
    "    '''\n",
    "    该类用于处理并查集初始化的恒等映射\n",
    "    '''\n",
    "    def __missing__(self, key):\n",
    "        return key\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n=None):\n",
    "        self.parent = IdentityDefaultDict()\n",
    "        if n: self.parent = list(range(n))\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    def merge(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y: self.parent[x] = y\n",
    "    def count_groups(self):\n",
    "        return len(set(self.find(x) for x in self.parent))\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        for x, y in allowedSwaps:\n",
    "            uf.merge(x, y)\n",
    "        n = len(source)\n",
    "        g1, g2 = defaultdict(list), defaultdict(list)\n",
    "        for i in range(n):\n",
    "            g1[uf.find(i)].append(source[i])\n",
    "            g2[uf.find(i)].append(target[i])\n",
    "\n",
    "        ans = 0\n",
    "        for k in g1:\n",
    "            c1, c2 = Counter(g1[k]), Counter(g2[k])\n",
    "            for k2 in set(list(c1.keys()) + list(c2.keys())):\n",
    "                ans += max(c1[k2], c2[k2]) - min(c1[k2], c2[k2])\n",
    "            \n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n = len(source)\n",
    "        f = {i:i for i in range(n)}\n",
    "\n",
    "        def find(x):\n",
    "            # print(f[x])\n",
    "            if f[x] != x:\n",
    "                f[x] = find(f[x])\n",
    "            return f[x]\n",
    "        \n",
    "        for a, b in allowedSwaps:\n",
    "            ta, tb = find(a), find(b)\n",
    "            if ta != tb:\n",
    "                f[ta] = tb\n",
    "        \n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a = find(i)\n",
    "            dic[a].append(i)\n",
    "\n",
    "        count = 0\n",
    "        \n",
    "        for k, v in dic.items():\n",
    "            a = Counter([source[i] for i in v])\n",
    "            b = Counter([target[i] for i in v])\n",
    "            count += len(list((a&b).elements()))\n",
    "        return n - count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int:\n",
    "        n=len(source)\n",
    "        parent={i:i for i in range(n)}\n",
    "        # 并查集\n",
    "        def find(x):\n",
    "            if x!=parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        # 搜索根节点\n",
    "        for l,r in allowedSwaps:\n",
    "            a,b=find(l),find(r)\n",
    "            if a!=b:\n",
    "                parent[b]=a\n",
    "\n",
    "        # 获取根节点对应的连通块。注意这里是按下标不是按具体值。\n",
    "        dic=collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            a=find(i)\n",
    "            dic[a].append(i)\n",
    "        print('dic', dic)\n",
    "\n",
    "        res=0\n",
    "        # 计算每个连通块对应的source元素与target的差集。如位置[0, 1]可以互换，坐标[0,1]在source中对应[2,3]，在target中对应[2, 4]，那么这一段连通块的差值就是1。\n",
    "        for k,v in dic.items():\n",
    "            a=[source[i] for i in v]\n",
    "            b=Counter([target[i] for i in v])\n",
    "            print('a', a)\n",
    "            print('b', b)\n",
    "            for c in a:\n",
    "                if b[c]>0:\n",
    "                    b[c]-=1\n",
    "                else:\n",
    "                    res+=1\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
